#include <iostream>
#include <algorithm>
#include <string>
#include <stack>
#include <set>
#include <queue>
#include <vector>
#include <map>
#include <fstream>
using namespace std;


/*---------------------------------数据结构--------------------------------*/
//路径三元组<起点,终点,字符>
typedef struct{
    int start;//起点
    int terminal;//终点
    char Character;//字符
}edge;

//NFA数据结构
typedef struct{
    /*-------------------字符集-------------------*/
    vector<char> CharacterVec;//字符集合
    
    /*-------------------状态集-------------------*/
    vector<int> StateVec;//状态集合
    
    /*-------------------初始状态-------------------*/
    int BeginState;//初始状态
    
    /*-------------------终止状态-------------------*/
    int EndState;//终止状态
    
    /*-------------------路径集合-------------------*/
    vector<edge> TranslationVec;//路径集合
    
}NFA;

//DFA数据结构
typedef struct{
    /*-------------------字符集-------------------*/
    vector<char> CharacterVec;//字符集合
    
    /*-------------------状态集-------------------*/
    vector<int> StateVec;//状态集合
    
    /*-------------------初始状态-------------------*/
    int BeginState;//初始状态
    
    /*-------------------终止状态-------------------*/
    set<int> EndStateVec;//终止状态集合
    
    /*-------------------转换表-------------------*/
    vector< vector<int> > TranslationTable;
    
}DFA;





/*----------------------------中缀表达式->后缀表达式--------------------------------*/
void change(string mid,string &beh){
    beh="";
    stack<char> s;
    map<char,int> op;
    op['(']=0;
    op[')']=0;
    op['|']=1;
    op['.']=2;
    op['*']=3;
    string::iterator it=mid.begin();
    
    while(it!=mid.end()){
        //如果有空格，则删除字符串中的空格
        if(*it==' '){
            mid.erase(it);
            continue;
        }
        //if （ 操作数 || '(' ） 之前出现（ '*' || ')' || 操作数 ) 则添加'.'
        if( it!=mid.begin() && (op.count(*it)==0 || *it=='(') && (*(it-1)==')' || *(it-1)=='*' || op.count(*(it-1))==0 ) ){
            mid.insert(it, '.');
            it++;
        }
        it++;
    }
    it=mid.begin();
    while(it!=mid.end()){
        if(op.count(*it)){//如果改元素为运算符的话
            if(*it==')'){//若为’）‘，把栈中的运算符依次加入后缀表达式，直到出现'（'，’（‘出栈，退出该次循环
                while (s.top()!='('){
                    beh+=s.top();
                    s.pop();
                }
                s.pop();
            }else if(s.empty() || *it=='(' || op[*it]>op[s.top()]){
                s.push(*it);
            }else if(op[*it]<=op[s.top()]){
                while (op[*it]<=op[s.top()] && (!s.empty())) {
                    beh+=s.top();
                    s.pop();
                    if(s.empty()) break;
                }
                s.push(*it);
            }
        }
        else{//如果是数字的话
            beh+=*it;
        }
        it++;
        //当中缀表达式输出完成，所有元素出栈
        if(it==mid.end()){
            while(!s.empty()){
                beh+=s.top();
                s.pop();
            }
            break;
        }
    }
    //解决简单的成环问题！！！
    it=beh.begin();
    while (it!=beh.end()) {
        if(*it=='*'&& (it+1)!=beh.end() && *(it+1)=='*'){
            beh.erase(it+1);
            continue;
        }
        it++;
    }
}







/*----------------------------Thompson算法生成NFA--------------------------------*/

//初始化nfa最小单元
NFA * createSmallNFA(char c,int &num){
    NFA *nfa = new NFA();
    
    //字符集初始化
    nfa->CharacterVec.push_back(' ');
    nfa->CharacterVec.push_back(c);
    
    //状态集合初始化
    nfa->StateVec.push_back(num);
    nfa->StateVec.push_back(num+1);
    
    //初始状态初始化
    nfa->BeginState=num;
    
    //终止状态初始化
    nfa->EndState=num+1;
    
    //更新num的值
    num+=2;
    
    //路径集合初始化
    edge e;
    e.start=nfa->BeginState;e.terminal=nfa->EndState;e.Character=c;
    nfa->TranslationVec.push_back(e);
    
    return nfa;
}

//汤普森算法-连接运算
NFA * ThompsonConnect(NFA* nfa_a,NFA* nfa_b){
    /*把nfa_b合并到nfa_a中去,并增加一条链接路径*/
    
    //首先合并字符集
    for(int i=0;i<nfa_b->CharacterVec.size();i++){
        vector<char>::iterator it;
        it=find(nfa_a->CharacterVec.begin(),nfa_a->CharacterVec.end(),nfa_b->CharacterVec[i]);
        if(it==nfa_a->CharacterVec.end())
            nfa_a->CharacterVec.push_back(nfa_b->CharacterVec[i]);
    }
    
    //合并状态集
    for(int i=0;i<nfa_b->StateVec.size();i++){
        nfa_a->StateVec.push_back(nfa_b->StateVec[i]);
    }
    
    //更新路径集合
    for(int i=0;i<nfa_b->TranslationVec.size();i++){
        nfa_a->TranslationVec.push_back(nfa_b->TranslationVec[i]);
    }
    //增加一条nfa_a到nfa_b的空转移路径
    edge e;
    e.start=nfa_a->EndState;e.terminal=nfa_b->BeginState;e.Character=' ';
    nfa_a->TranslationVec.push_back(e);
    
    //更新终止状态
    nfa_a->EndState=nfa_b->EndState;
    
    
    //释放空间
    delete nfa_b;
    
    return nfa_a;
}

//汤普森算法-或运算
NFA * ThompsonOr(NFA* nfa_a,NFA* nfa_b,int &num){
    /*把nfa_b合并到nfa_a中去，并增加两个状态和四条空转移路径*/
    
    
    //首先合并字符集
    for(int i=0;i<nfa_b->CharacterVec.size();i++){
        vector<char>::iterator it;
        it=find(nfa_a->CharacterVec.begin(),nfa_a->CharacterVec.end(),nfa_b->CharacterVec[i]);
        if(it==nfa_a->CharacterVec.end())
            nfa_a->CharacterVec.push_back(nfa_b->CharacterVec[i]);
    }
    
    //合并状态集
    for(int i=0;i<nfa_b->StateVec.size();i++){
        nfa_a->StateVec.push_back(nfa_b->StateVec[i]);
    }
    
    //添加两个状态
    nfa_a->StateVec.push_back(num);
    nfa_a->StateVec.push_back(num+1);
    
    //更新路径集合
    for(int i=0;i<nfa_b->TranslationVec.size();i++){
        nfa_a->TranslationVec.push_back(nfa_b->TranslationVec[i]);
    }
    
    //增加四条空转移路径
    edge a,b,c,d;
    a.start=num;a.terminal=nfa_a->BeginState;a.Character=' ';
    nfa_a->TranslationVec.push_back(a);
    b.start=num;b.terminal=nfa_b->BeginState;b.Character=' ';
    nfa_a->TranslationVec.push_back(b);
    c.start=nfa_a->EndState;c.terminal=num+1;c.Character=' ';
    nfa_a->TranslationVec.push_back(c);
    d.start=nfa_b->EndState;d.terminal=num+1;d.Character=' ';
    nfa_a->TranslationVec.push_back(d);
    
    
    //更新初始状态
    nfa_a->BeginState=num;
    //更新终止状态
    nfa_a->EndState=num+1;
    
    
    //释放空间
    delete nfa_b;
    
    //更新num的值
    num+=2;
    
    return nfa_a;
}

//汤普森算法-闭包运算
NFA * ThompsonClosure(NFA* nfa,int &num){
    //添加两个状态
    nfa->StateVec.push_back(num);
    nfa->StateVec.push_back(num+1);
    
    //添加四条路径
    edge a,b,c,d;
    a.start=num;a.terminal=nfa->BeginState;a.Character=' ';
    nfa->TranslationVec.push_back(a);
    b.start=nfa->EndState;b.terminal=num+1;b.Character=' ';
    nfa->TranslationVec.push_back(b);
    c.start=num;c.terminal=num+1;c.Character=' ';
    nfa->TranslationVec.push_back(c);
    d.start=nfa->EndState;d.terminal=nfa->BeginState;d.Character=' ';
    nfa->TranslationVec.push_back(d);
    
    //修改初始状态
    nfa->BeginState=num;
    
    //修改终止状态
    nfa->EndState=num+1;
    
    //维护num
    num+=2;
    
    return nfa;
}


NFA * CreateNFA(string zhengguishi_houzhui){
    //定义num为编码NFA中状态的全局变量
    int num=0;
    
    //初始化栈s,存储生成nfa过程中的指针
    stack<NFA *> s;
    
    //遍历后缀表达式，生成NFA
    for(int i=0;i<zhengguishi_houzhui.length();i++){
        char c=zhengguishi_houzhui[i];
        if(c=='|' || c=='.' || c=='*'){
            //如果字符是|或.或*中的一种，泽峰情况执行三种Thompson算法
            if(c=='|'){
                //执行 | 的汤普森算法
                //出栈第一个指针为nfa_b
                NFA *nfa_b = s.top();
                s.pop();
                //出栈第二个指针为nfa_a
                NFA *nfa_a = s.top();
                s.pop();
                //合并得到新的nfa，并压栈
                NFA *new_nfa = ThompsonOr(nfa_a, nfa_b,num);
                s.push(new_nfa);
                
                
            }else if(c=='.'){
                //执行 . 的汤普森算法
                //出栈第一个指针为nfa_b
                NFA *nfa_b = s.top();
                s.pop();
                //出栈第二个指针为nfa_a
                NFA *nfa_a = s.top();
                s.pop();
                //合并得到新的nfa,并压栈
                NFA *new_nfa = ThompsonConnect(nfa_a, nfa_b);
                s.push(new_nfa);
                
            }else{
                //执行 * 的汤普森算法
                //出栈第一个指针为nfa
                NFA *nfa = s.top();
                s.pop();
                NFA *new_nfa = ThompsonClosure(nfa, num);
                s.push(new_nfa);
                
            }
        }else{
            //如果遇到字符，则创建最小NFA，并压栈
            NFA * nfa = createSmallNFA(c,num);
            s.push(nfa);
        }
    }
    
    return s.top();
}




/*-------------------------------NFA->minDFA-----------------------------------*/

//判断Sigma列是否为空
int isSigmaEmpty(vector<vector<vector<int> > > TranslationTable){
    for(int i=0;i<TranslationTable.size();i++){
        if(TranslationTable[i][0].size()!=0){
            return 0;
        }
    }
    return 1;
}

DFA * NFAtoDFA(NFA * nfa){
    
    //定义NFA转换表
    //NFA转换表的行数
    int row=(int)nfa->StateVec.size();
    //NFA转换表的列数
    int col=(int)nfa->CharacterVec.size();
    //NFA转换表：用vector定义的三维数组，并进行行数和列数的初始化
    vector<vector<vector<int> > > TranslationTable(row, vector<vector<int> >(col,vector<int>(0)));
    //定义终态集合
    vector<int> EndStateVec;
    EndStateVec.push_back(nfa->EndState);
    
    
    //---------------NFA转换表赋值-------------------
    for(int i=0;i<nfa->TranslationVec.size();i++){
        //取出三元组，c为字符,start为起始点，terminal为终止点
        char c=nfa->TranslationVec[i].Character;
        int start=nfa->TranslationVec[i].start;
        int terminal=nfa->TranslationVec[i].terminal;
        //搜索字母下标
        int index=0;
        for(;index<nfa->CharacterVec.size();index++){
            if(c==nfa->CharacterVec[index]){
                break;
            }
        }
        //赋值
        TranslationTable[start][index].push_back(terminal);
    }
    
    
    //-------------------子集构造法，消除空转移------------------
    //！！！如果要消除环问题，在这个地方解决！！！
    while(!isSigmaEmpty(TranslationTable)){
        //只要TranslationTable的Sigma列（第0列）不为空，就一直执行
        for(int i=0;i<TranslationTable.size();i++){
            if(TranslationTable[i][0].size()!=0){
                int num=TranslationTable[i][0][0];
                //如果在终态集合里面，则标记为终态集合
                vector<int>::iterator it1=find(EndStateVec.begin(), EndStateVec.end(), num);
                vector<int>::iterator it2=find(EndStateVec.begin(), EndStateVec.end(), i);
                if(it1!=EndStateVec.end() && it2==EndStateVec.end()){
                    EndStateVec.push_back(i);
                }
                //如果关联的num行中，里面的Sigma列为空，则将num行中的内容赋值到i行中
                if(TranslationTable[num][0].size()==0){
                    for(int j=1;j<TranslationTable[i].size();j++){
                        TranslationTable[i][j].insert(TranslationTable[i][j].end(),TranslationTable[num][j].begin(),TranslationTable[num][j].end());
                    }
                    //删除i行里面的Sigma列中的值，每次只遍历第一个元素，删到空为止
                    TranslationTable[i][0].erase(TranslationTable[i][0].begin());
                }
            }
        }
    }
    
    
    //-----------------------DFA表的改名-------------------------
    //定义DFATable改名后的DFA转换表
    vector<vector<int> > DFATable;
    
    //定义DFAmap为DFA改名映射表
    map<set<int> , int> DFAmap;
    
    //定义newEndStateVec改名后的DFA终态集合
    vector<int> newEndStateVec;
    
    //设定一个改名全局变量
    int SetNum=0;
    
    //找到初始位置，故初态为0
    set<int> BeginStateSet;
    BeginStateSet.insert(nfa->BeginState);
    DFAmap[BeginStateSet]=SetNum++;
    
    //定义DFAqueue为DFA改名中的辅助队列（原理是bfs）
    queue<set<int> >DFAqueue;
    DFAqueue.push(BeginStateSet);
    
    while (!DFAqueue.empty()) {
        //取出当前队列中的第一个集合
        set<int> tempSet=DFAqueue.front();
        DFAqueue.pop();
        
        //设定tempVec为新表的一行
        vector<int> tempVec;
        //循环处理每一个字符的内容
        for(int i=1;i<col;i++){
            //遍历set，计算这个字符所到达的状态集合
            set<int> ReachSet;
            for(set<int>::iterator it=tempSet.begin();it!=tempSet.end();it++){
                for(int j=0;j<TranslationTable[*it][i].size();j++){
                    ReachSet.insert(TranslationTable[*it][i][j]);
                }
            }
            if(ReachSet.size()>0){
                //如果能到达
                if(DFAmap.count(ReachSet)==0){
                    //如果不在改名映射表中
                    DFAmap[ReachSet]=SetNum++;
                    DFAqueue.push(ReachSet);
                }
                tempVec.push_back(DFAmap[ReachSet]);
            }else{
                //如果不能到达
                tempVec.push_back(-1);
            }
        }
        DFATable.push_back(tempVec);
        
        //更新终态集合
        for(set<int>::iterator it=tempSet.begin();it!=tempSet.end();it++){
            //如果*it在终态集合EndStateVec且不在新终态集合newEndStateVec中，新终态集合newEndStateVec中添加map[tempSet]
            vector<int>::iterator it1=find(EndStateVec.begin(), EndStateVec.end(), *it);
            vector<int>::iterator it2=find(newEndStateVec.begin(), newEndStateVec.end(), *it);
            if(it1!=EndStateVec.end() && it2==newEndStateVec.end()){
                newEndStateVec.push_back(DFAmap[tempSet]);
                break;
            }
        }
    }
    
    
    
    
    
    //---------------------------DFA->minDFA---------------------------
    //定义终态集合
    set<int> S1;
    //定义初态集合
    set<int> S2;
    //定义集合分裂成的集合列表
    vector<set<int> > minDFAQueue;
    
    //将集合分为初态和终态
    for(int i=0;i<DFATable.size();i++){
        vector<int>::iterator it=find(newEndStateVec.begin(), newEndStateVec.end(), i);
        if(it==newEndStateVec.end()){
            S2.insert(i);
        }else{
            S1.insert(i);
        }
    }
    //初始化集合列表，为终态集和初态集
    minDFAQueue.push_back(S1);
    minDFAQueue.push_back(S2);
    
    
    while(1){
        //flag为跳出条件，如果经历一次循环，minDFAQueue集合没有变化，则跳出，说明已经分裂完成了！
        int flag=0;
        
        for(int i=0;i<minDFAQueue.size();i++){
            //tempDFAQueue用于记录minDFAQueue[i]所分裂出的集合列表
            vector<set<int> > tempDFAQueue;
            //找到一个可以分解的set
            for(set<int>::iterator it=minDFAQueue[i].begin();it!=minDFAQueue[i].end();it++){
                //寻找*it是否在某个tempDFAQueue集合列表里面的某个集合,得到下标j
                int j;
                for(j=0;j<tempDFAQueue.size();j++){
                    
                    int isSameSet=1;
                    int a = *tempDFAQueue[j].begin();
                    int b = *it;
                    for(int k=0;k<DFATable[a].size();k++){
                        //需要考虑到-1的情况
                        if(DFATable[a][k]!=-1 && DFATable[b][k]!=-1 ){//如两个值都不等于-1，需要额外判断
                            int index_a=0;int index_b=0;
                            for(int l=0;l<minDFAQueue.size();l++){
                                if(minDFAQueue[l].count(DFATable[a][k])==1){
                                    index_a=l;
                                }
                                if(minDFAQueue[l].count(DFATable[b][k])==1){
                                    index_b=l;
                                }
                            }
                            if(index_a!=index_b){
                                isSameSet=0;
                            }
                        }else if(DFATable[a][k]==-1 && DFATable[b][k]==-1){//如果两个值都等于-1，保持原状
                            
                        }else{//如果一个值等于-1，一个值不等于-1，则不相等
                            isSameSet=0;
                        }
                    }
                    //如果DFATable[a][k] 和 DFATable[b][k]是在一个集合里面，则插入到tempDFAQueue[j]中
                    if( isSameSet ){
                        tempDFAQueue[j].insert(*it);
                        break;
                    }
                }
                //如果下标j==tempDFAQueue.size()，则说明应该另外分裂出一个新的set
                if(j==tempDFAQueue.size()){
                    set<int> tempS;
                    tempS.insert(*it);
                    tempDFAQueue.push_back(tempS);
                }
            }
            //tempDFAQueue.size()>1则代表可以分解，分解完成后break，要重新遍历整个循环
            if(tempDFAQueue.size()>1){
                //做分裂的时候要标记flag=1，代表有分裂，还需要再进行循环判断是否还可以分裂
                flag=1;
                //把tempDFAQueue中的集合添加到minDFAQueue中
                for(int j=0;j<tempDFAQueue.size();j++){
                    minDFAQueue.push_back(tempDFAQueue[j]);
                }
                //删除minDFAQueue中被分裂的集合
                minDFAQueue.erase(minDFAQueue.begin() + i);
                break;
            }
        }
        
        if(flag==0){
            break;
        }
    }
    

    //---------------------------minDFA二维数组改名---------------------------
    //定义minDFANum为改名时的全局变量
    int minDFANum=0;
    //minDFAmap为set集合改名为int的映射表
    map<set<int> , int > minDFAmap;
    //定义minDFAEndVec为改名后的终态集合
    set<int> minDFAEndVec;
    //定义minDFABegin为改名后的初态
    int minDFABegin=0;
    
    for(int i=0;i<minDFAQueue.size();i++){
        //添加集合改名后的映射关系
        minDFAmap[minDFAQueue[i]]=minDFANum++;
        
        //初始化 终态集合和初态
        for(set<int>::iterator it=minDFAQueue[i].begin();it!=minDFAQueue[i].end();it++){
            //如果集合中有初态，则为初态
            if(*it==0){
                minDFABegin=minDFAmap[minDFAQueue[i]];
            }
            //如果集合中有终态存在，则为终态集合
            vector<int>::iterator in_it1=find(newEndStateVec.begin(), newEndStateVec.end(), *it);
            if( in_it1!=newEndStateVec.end() ){
                minDFAEndVec.insert(minDFABegin=minDFAmap[minDFAQueue[i]]);
            }
        }
    }
    
    //设定minDFATable为改名后的表
    vector<vector<int> > minDFATable;
    
    for(int i=0;i<minDFAQueue.size();i++){
        int now=*minDFAQueue[i].begin();
        vector<int> tempMinDFAVec;
        for(int j=0;j<DFATable[i].size();j++){
            if(DFATable[now][j]==-1){
                //如果是-1，则还是-1
                tempMinDFAVec.push_back(-1);
            }else{
                //如果不是-1，做映射,找到DFATable[now][j]所在的集合的映射
                for(int k=0;k<minDFAQueue.size();k++){
                    if(minDFAQueue[k].count(DFATable[now][j])==1){
                        tempMinDFAVec.push_back(minDFAmap[minDFAQueue[k]]);
                    }
                }
            }
        }
        minDFATable.push_back(tempMinDFAVec);
    }
    

    //---------------------------生成minDFA---------------------------
    DFA *dfa = new DFA();
    //字符集
    for(int i=1;i<col;i++){
        dfa->CharacterVec.push_back(nfa->CharacterVec[i]);
    }
    
    //状态集合
    for(int i=0;i<minDFATable.size();i++){
        dfa->StateVec.push_back(i);
    }
    
    //初始状态
    dfa->BeginState=minDFABegin;
    
    //终止状态集合
    for(set<int>::iterator it=minDFAEndVec.begin();it!=minDFAEndVec.end();it++){
        dfa->EndStateVec.insert(*it);
    }
    //转换表
    for(int i=0;i<minDFATable.size();i++){
        dfa->TranslationTable.push_back(minDFATable[i]);
    }
    
    //---------------------------返回minDFA---------------------------
    return dfa;
}


/*---------------------------判断word是否符合正规式--------------------------------*/
int isFulfill(string word,DFA *dfa){
    //从初始状态开始走
    int State=dfa->BeginState;
    
    //遍历word中的每一个单词
    for(int i=0;i<word.length();i++){
        
        //寻找到当前字符word[i]对应的CharacterVec中的下标为j
        int j=0;
        for(;j<dfa->CharacterVec.size();j++){
            if(dfa->CharacterVec[j]==word[i]){
                break;
            }
        }
        
        //如果word[i]不在CharacterVec中，则不符合正规式，返回0
        if(j==dfa->CharacterVec.size()){
            return 0;
        }
        //State等于下一个状态
        State=dfa->TranslationTable[State][j];
        //如果出现State等于-1,也就是通过word[i]无通路，即不可走，故不符合正规式，返回0
        if(State==-1){
            return 0;
        }
    }
    
    //如果State最终停留的位置不在终态集合，不符合正规式，返回0
    if(dfa->EndStateVec.count(State)==0){
        return 0;
    }
    
    //以上情况均满足，复合正规式，返回1
    return 1;
}




/*------------------------------从源文件到正规式-----------------------------------*/

vector<string> RE_vec;
vector<string> RE_NAME_vec;
set<string> KEYWORDS_SET;
set<string> OPERATOR_SET;
set<string> SEPARATOR_SET;
vector<DFA *> DFA_Vec;

vector<DFA *> CreateDFAVec(vector<string> RE_vec){
    vector<DFA *> DFAVec;
    for(int i=0;i<RE_vec.size();i++){
        //生成后缀表达式
        string zhengguishi_houzhui = "";
        change(RE_vec[i],zhengguishi_houzhui);
        /*----------------------后缀表达式->NFA(Thompson)--------------------------*/
        NFA * nfa = CreateNFA(zhengguishi_houzhui);
        
        //NFA 输出测试
        cout<<"##########NFA输出测试##########"<<endl;
        cout<<"#字符集合："<<endl;
        for(int i=0;i<nfa->CharacterVec.size();i++){
            cout<<nfa->CharacterVec[i]<<" ";
        }
        cout<<endl;
        
        cout<<"#状态集合："<<endl;
        for(int i=0;i<nfa->StateVec.size();i++){
            cout<<nfa->StateVec[i]<<" ";
        }
        cout<<endl;
        
        cout<<"#初态："<<endl;
        cout<<nfa->BeginState<<endl;
        
        cout<<"#终态："<<endl;
        cout<<nfa->EndState<<endl;
        
        cout<<"#路径集合："<<endl;
        for(int i=0;i<nfa->TranslationVec.size();i++){
            cout<<" < "<<nfa->TranslationVec[i].start<<" "<<nfa->TranslationVec[i].terminal<<" "<<nfa->TranslationVec[i].Character<<" > "<<endl;
        }
        cout<<"##########NFA输出测试##########"<<endl;
        //NFA 输出结束
        
        
        
        
        /*----------------------------NFA->minNFA--------------------------------*/
        DFA *dfa = NFAtoDFA(nfa);
        DFAVec.push_back(dfa);
        //DFA 输出测试
        cout<<"##########DFA输出测试##########"<<endl;
        cout<<"#字符集合："<<endl;
        for(int i=0;i<dfa->CharacterVec.size();i++){
            cout<<dfa->CharacterVec[i]<<" ";
        }
        cout<<endl;
        
        cout<<"#状态集合："<<endl;
        for(int i=0;i<dfa->StateVec.size();i++){
            cout<<dfa->StateVec[i]<<" ";
        }
        cout<<endl;
        
        cout<<"初态集合："<<endl;
        cout<<dfa->BeginState<<endl;
        
        cout<<"#终态集合："<<endl;
        for(set<int>::iterator it=dfa->EndStateVec.begin();it!=dfa->EndStateVec.end();it++){
            cout<<*it<<" ";
        }
        cout<<endl;
        
        cout<<"#转换表："<<endl;
        for(int i=0;i<dfa->TranslationTable.size();i++){
            for(int j=0;j<dfa->TranslationTable[i].size();j++){
                cout<<dfa->TranslationTable[i][j]<<" ";
            }
            cout<<endl;
        }
        cout<<"##########DFA输出测试##########"<<endl;
        //DFA 输出结束
        
        
    }
    return DFAVec;
}

string StandardStr(string str){
    if( !str.empty() )
    {
        str.erase(0,str.find_first_not_of("\t"));
        str.erase(str.find_last_not_of("\t") + 1);
        str.erase(0,str.find_first_not_of(" "));
        str.erase(str.find_last_not_of(" ") + 1);
    }
    string newstr="";
    for(int i=0;i<str.length();i++)
    {
        if(str[i]=='\t'){
            str[i]=' ';
        }
        if(str[i]==' '&&str[i+1]==' '){
            continue;
        }
        newstr+=str[i];
    }
    return newstr;
}

void SourceFileToMarkStreams(string filename){
    ifstream fin;
    fin.open(filename, ios::in);
    
    ofstream fout;
    string outfile =filename +"_res";
    fout.open(outfile, ios::out);
    
    
    if (!fin.is_open()){
        cout << "open inFile Failed." << endl;
    }
    if (!fout.is_open()){
        cout << "open outFile Failed." << endl;
    }
    
    
    string str;
    while ( getline(fin,str) )
    {
        str=StandardStr(str);
        if(str[0]=='#'){//宏定义
            cout<<"< "<<str<<" , "<<"宏定义"<<" >"<<endl;
            fout<<"< "<<str<<" , "<<"宏定义"<<" >"<<endl;
            continue;
        }
        
        //读一个，贪心往后读
        for(int i=0;i<str.length();){
            string min_str="";
            
            if(isalpha(str[i]) || isdigit(str[i]) || str[i]=='_'){
                while( isalpha(str[i]) || isdigit(str[i]) || str[i]=='_' || str[i]=='.'){
                    if(str[i]=='.'){
                        min_str+='^';
                    }else{
                        min_str+=str[i];
                    }
                    i++;
                }
                if(KEYWORDS_SET.count(min_str)){
                    cout<<"< "<<min_str<<" , "<<"关键字"<<" >"<<endl;
                    fout<<"< "<<min_str<<" , "<<"关键字"<<" >"<<endl;
                }else{
                    int i;
                    for(i=0;i<DFA_Vec.size();i++){
                        if(isFulfill(min_str,DFA_Vec[i])){
                            //输出
                            cout<<"< ";
                            fout<<"< ";
                            for(int ss=0;ss<min_str.length();ss++){
                                if(min_str[ss]=='^'){
                                    cout<<'.';
                                    fout<<'.';
                                }else{
                                    cout<<min_str[ss];
                                    fout<<min_str[ss];
                                }
                            }
                            cout<<" , "<<RE_NAME_vec[i]<<" >"<<endl;
                            fout<<" , "<<RE_NAME_vec[i]<<" >"<<endl;
                            break;
                            
                        }
                    }
                    if(i==DFA_Vec.size()){
                        cout<<"< "<<min_str<<" , "<<"无法识别"<<" >"<<endl;
                        fout<<"< "<<min_str<<" , "<<"无法识别"<<" >"<<endl;
                    }
                }
            }else if(str[i]=='/' && i+1<str.length() && (str[i+1]=='/' || str[i+1]=='*') ) {
                min_str="";
                for(;i<str.length();i++){
                    min_str+=str[i];
                }
                cout<<"< "<<min_str<<" , "<<"注释"<<" >"<<endl;
                fout<<"< "<<min_str<<" , "<<"注释"<<" >"<<endl;
            }
            else{
                min_str += str[i];
                //是分隔符
                if(SEPARATOR_SET.count(min_str)){
                    cout<<"< "<<min_str<<" , "<<"分隔符"<<" >"<<endl;
                    fout<<"< "<<min_str<<" , "<<"分隔符"<<" >"<<endl;
                    i++;
                }
                else if(min_str==" "){
                    i++;
                }
                else{
                    string tempstr=min_str;
                    if(i+1<str.length()){
                        tempstr+=str[i+1];
                    }
                    if(OPERATOR_SET.count(tempstr))
                    {
                        cout<<"< "<<tempstr<<" , "<<"操作符"<<" >"<<endl;
                        fout<<"< "<<tempstr<<" , "<<"操作符"<<" >"<<endl;
                        i+=2;
                    }
                    else if(OPERATOR_SET.count(min_str)){
                        cout<<"< "<<min_str<<" , "<<"操作符"<<" >"<<endl;
                        fout<<"< "<<min_str<<" , "<<"操作符"<<" >"<<endl;
                        i++;
                    }else{
                        cout<<"< "<<min_str<<" , "<<"无法识别"<<" >"<<endl;
                        fout<<"< "<<min_str<<" , "<<"无法识别"<<" >"<<endl;
                        i++;
                    }
                }
            }
        }
    }
}

void InitData(){
    /*---------------------------关键词初始化----------------------------------*/
    string KEYWORDS[71] = {
        "void","int","char","float","double","bool","w_char",
        "struct","union","enum","class","typedef",
        "true","false",
        "long","short","singed","unsigned",
        "const","volatile","restrict",
        "auto","register","static","extern","thread_local","mutable",
        "inline","asm",
        "for","while","do",
        "break","continue","return","goto",
        "if","else","switch","case","default",
        "new","delete",
        "sizeof","and","and_eq","bitand","bitor","compl","not","not_eq","or","or_eq","xor","xor_eq",
        "this","friend","virtual","mutable","explicit","operator",
        "private","protected","public",
        "template","typename",
        "namespace","using",
        "throw","try","catch",
    };
    
    for(int i=0;i<sizeof(KEYWORDS)/sizeof(KEYWORDS[0]);i++){
        KEYWORDS_SET.insert(KEYWORDS[i]);
    }
    
    /*---------------------------操作符初始化----------------------------------*/
    string OPERATOR[35]={"+","-","*","/","%","++","--",">","<","==",">=","<=","<>","!=","&&","||","!","&","|","~","^","<<",">>","=","+=","-=","*=","/=","%=","&=","|=","^=","?:","*","&"};
    
    for(int i=0;i<sizeof(OPERATOR)/sizeof(OPERATOR[0]);i++){
        OPERATOR_SET.insert(OPERATOR[i]);
    }
    
    /*---------------------------分隔符初始化----------------------------------*/
    string SEPARATOR[9]={",",";","(",")","{","}",":","[","]"};
    
    for(int i=0;i<sizeof(SEPARATOR)/sizeof(SEPARATOR[0]);i++){
        SEPARATOR_SET.insert(SEPARATOR[i]);
    }
    
    
}

void InitRegularExpression(){
    /*---------------------------整数----------------------------------*/
    string RE_INTEGER="(0|1|2|3|4|5|6|7|8|9).(0|1|2|3|4|5|6|7|8|9)*";
    RE_vec.push_back(RE_INTEGER);
    RE_NAME_vec.push_back("整数");
    
    /*---------------------------浮点数----------------------------------*/
    string RE_FLOAT="((0|1|2|3|4|5|6|7|8|9).(0|1|2|3|4|5|6|7|8|9)*).^.((0|1|2|3|4|5|6|7|8|9).(0|1|2|3|4|5|6|7|8|9)*)";
    RE_vec.push_back(RE_FLOAT);
    RE_NAME_vec.push_back("浮点数");
    
    /*---------------------------标识符----------------------------------*/
    string RE_IDENTIFIER="(a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|_).(a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|_0|1|2|3|4|5|6|7|8|9)*";
    RE_vec.push_back(RE_IDENTIFIER);
    RE_NAME_vec.push_back("标识符");
}



/*----------------------------------主函数---------------------------------------*/
int main(int argc, const char * argv[]) {
    /*---------------------------初始化----------------------------------*/
    InitData();//初始化关键字、分隔符、操作符
    InitRegularExpression();//初始化正规式集合
    
    /*---------------------------生成DFA序列----------------------------------*/
    DFA_Vec = CreateDFAVec(RE_vec);
    
    /*---------------------------文件流读取模块----------------------------------*/
    string filename = "/Users/wengyifan/Desktop/test/test02.cpp";
    SourceFileToMarkStreams(filename);
}
$












